iT邦幫忙

2022 iThome 鐵人賽

0
自我挑戰組

30天 Neetcode解題之路系列 第 29

Day 29 - 704. Binary Search

  • 分享至 

  • xImage
  •  

前言

大家好,我是毛毛。ヾ(´∀ ˋ)ノ
那就開始今天的解題吧~


Question

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Think

題目給一個從小到大排的數字list(nums)與一個數字(target),要找出target這個數位於list中的index,如果都找不到就回傳-1

基本上就是如題目意思做Binary Search
首先宣告三個變數,midleftright

  • mid = 0
  • left = 0
  • right = len(nums) - 1

接著,就是對半對半的砍,目前right&left的中心mid

  1. mid = int((left + right) / 2)
  2. mid = (left + right) // 2)
  3. mid = left + ((right - left) / 2)
    上面三種都可以,第一個是算完如果得到小數,直接轉型成int,相當於無條件捨去小數點後的數;第二個是兩者相加除以2取商;第三種是我後來看到的,有點像是leftoffset的感覺。

最後,就是看我們的targetmid大還是小:

  1. 如果是target小於mid:代表targetmid左邊,所以我們把right設成mid - 1
  2. 如果是target大於mid:代表targetmid右邊,所以我們把left設成mid + 1
  3. 如果是target等於mid:代表我們找到啦~就直接回傳mid的值

如果整個跑完都沒有就表示,list找不到target這個值,就直接回傳-1

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        mid = 0
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = int((left + right) / 2)
            print(left, mid, right)
            if nums[mid] > target:
                right = mid -1
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid
            
        return -1

Submission


今天就到這邊啦~
大家明天見/images/emoticon/emoticon29.gif


上一篇
Day 28 - 739. Daily Temperatures (By C++)
下一篇
Day 30 - 704. Binary Search (By C++)
系列文
30天 Neetcode解題之路30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言